package baseclass.h_heap;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 寻找数据流的中位数：
 * 构建一个大跟堆一个小跟堆，二者容量只差小于等于1.
 * 大于大跟堆堆顶的元素放入小跟堆，否则放入大跟堆。
 * <p>
 * 这样可以保证，大根堆存的是小的数，
 * 小跟堆存的是大的数。
 * <p>
 * 中位数要么是二者堆顶(二者容量差1下)，要么是均值。
 *
 * @date 2020/2/29 21:27
 */
public class GetMedian {
    Queue<Integer> smallQ;
    Queue<Integer> bigQ;

    public GetMedian() {
        smallQ = new PriorityQueue<>();
        bigQ = new PriorityQueue<>((a, b) -> b - a);
    }

    public void insert(int e) {
        if (isEmpty()) {
            bigQ.add(e);
            return;
        }
        //here bigQ must has elements
        if (bigQ.peek() < e) {
            smallQ.add(e);
        } else {
            bigQ.add(e);
        }
        adjustQueue();
    }

    public int getMedian() {
        if (isEmpty()) throw new RuntimeException("empty");
        if (smallQ.size() == bigQ.size()) {
            return (smallQ.peek() + bigQ.peek()) / 2;
        }
        return smallQ.size() > bigQ.size() ?  smallQ.peek() : bigQ.peek();
    }


    private void adjustQueue() {
        if (Math.abs(smallQ.size() - bigQ.size()) > 1) {
            if (smallQ.size() > bigQ.size()) {
                bigQ.add(smallQ.poll());
            } else {
                smallQ.add(bigQ.poll());
            }
        }
    }

    private boolean isEmpty() {
        return smallQ.size() == 0 && bigQ.size() == 0;
    }

    // for test, this method is ineffective but absolutely right
    public static int getMedianOfArray(int[] arr) {
        int[] newArr = Arrays.copyOf(arr, arr.length);
        Arrays.sort(newArr);
        int mid = (newArr.length - 1) / 2;
        if ((newArr.length & 1) == 0) {
            return (newArr[mid] + newArr[mid + 1]) / 2;
        } else {
            return newArr[mid];
        }
    }


    public static void main(String[] args) {
        boolean err = false;
        int testTimes = 2000000;
        for (int i = 0; i != testTimes; i++) {
            int len = 30;
            int maxValue = 1000;
            int[] arr = getRandomArray(len, maxValue);
            GetMedian medianHold = new GetMedian();
            for (int j = 0; j != arr.length; j++) {
                medianHold.insert(arr[j]);
            }
            if (medianHold.getMedian() != getMedianOfArray(arr)) {
                err = true;
                printArray(arr);
                break;
            }
        }
        System.out.println(err ? "err" : "right");
    }


    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static int[] getRandomArray(int maxLen, int maxValue) {
        int[] res = new int[(int) (Math.random() * maxLen) + 1];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue);
        }
        return res;
    }
}
